package com.markhsiu.map;

//http://blog.csdn.net/u014376020/article/details/50475909
public class Kmp {
    private static String src = null;
    private static String parten = null;
    private static int[] next;
    private static int len;

    private Kmp(String src, String parten) {
        super();

    }

    public static boolean doPartten(String src, String parten) {
        // 初始化
        Kmp.src = src;
        Kmp.parten = parten;
        len = parten.length();
        next = new int[len];
        getNext();
        // 开始匹配
        int j = 0;
        int length = src.length();
        for (int i = 0; i < length; i++) {
            while (parten.charAt(j) != src.charAt(i)) {
                j = next[j];
                if ((j == 0 && parten.charAt(j) != src.charAt(i))) {
                    j = -1;
                    break;
                }
            }
            if (++j == len) {
                return true;
            }
        }
        return false;

    }

    private static void getNext() {
        next[0] = 0;
        for (int i = 1; i < len; i++) {
            for (int j = i - 1; j > 0; j--) {
                String s1 = parten.substring(0, j - 1);
                String s2 = parten.substring(i - j + 1, i);
                if (s1.equals(s2) && j > next[i]) {
                    next[i] = j - 1;
                }
            }
        }
    }
}